package com.hc.programming.linked;

import com.hc.programming.bean.ListNode;

import java.util.Arrays;

/**
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置
 * <p>
 * 示例 1：
 * {@link ./旋转链表-示例1.png}
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[4,5,1,2,3]
 * 示例 2：
 * {@link ./旋转链表-示例2.png}
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 * <p>
 * 提示：
 * 链表中节点的数目在范围 [0, 500] 内
 * -100 <= Node.val <= 100
 * 0 <= k <= 2 * 10^9
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/8/31 21:24
 */
public class 旋转链表 {
    public static void main(String[] args) {
        System.out.println(rotateRight(new ListNode(Arrays.asList(1, 2, 3, 4, 5)), 2));
        System.out.println(rotateRight(new ListNode(Arrays.asList(0, 1, 2)), 4));
    }

    public static ListNode rotateRight(ListNode head, int k) {
        if (head == null || k == 0) {
            return head;
        }
        int size = 0;
        ListNode p = head;
        ListNode last = null;
        while (p != null) {
            size++;
            last = p;
            p = p.next;
        }
        k %= size;
        if (k == 0) {
            return head;
        }
        ListNode p1 = head;
        ListNode p2 = null;
        k = size - k;
        while (k > 0) {
            k--;
            p2 = p1;
            p1 = p1.next;
        }
        last.next = head;
        p2.next = null;
        return p1;
    }
}
